{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 基于关联规则的商品关联挖掘"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 创建5条交易记录\n",
    "transactions = [[\"milk\", \"bread\"], \n",
    "                [\"butter\"], \n",
    "                [\"beer\", \"diapers\"],\n",
    "                [\"milk\", \"bread\", \"butter\"],\n",
    "                [\"bread\"]\n",
    "               ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "商品如下=> {'diapers', 'butter', 'milk', 'beer', 'bread'}\n",
      "商品总数=> 5\n",
      "商品编号=> {'diapers': 0, 'butter': 1, 'milk': 2, 'beer': 3, 'bread': 4}\n",
      "商品列表=> ['diapers', 'butter', 'milk', 'beer', 'bread']\n"
     ]
    }
   ],
   "source": [
    "# 循环遍历数据，将其放入set集合中，去除重复元素\n",
    "items = set([t for transaction in transactions for t in transaction ])\n",
    "print(\"商品集合=>\", items)\n",
    "num_items = len(items)\n",
    "print(\"商品总数=>\", num_items)\n",
    "item2id = {t:i for t,i in zip(items, range(num_items))}\n",
    "print(\"商品编号=>\", item2id)\n",
    "id2item = [t for t in items]\n",
    "print(\"商品列表=>\", id2item)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 自定义函数：使用整数代表商品子集"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Itemset 9 => [0 1 0 0 1] = ['diapers', 'beer']\n"
     ]
    }
   ],
   "source": [
    "def int2items(num, num_items):\n",
    "    items = []\n",
    "    for i in range(num_items):\n",
    "        if num%2:\n",
    "            items.append(id2item[i])\n",
    "        # num的二进制数右移一位，与商品编号的序号是相反的关系\n",
    "        num >>= 1\n",
    "    return items\n",
    "\n",
    "print(\"Itemset 9 => [0 1 0 0 1] =\", int2items(9, num_items))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 自定义函数：将商品子集转为整数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Items ['milk', 'butter'] = 6\n"
     ]
    }
   ],
   "source": [
    "def items2int(items, num_items):\n",
    "    id = 0\n",
    "    for i in items:\n",
    "        id += 2 ** item2id[i]\n",
    "    return id\n",
    "\n",
    "print(\"Items ['milk', 'butter'] => [0 0 1 1 0] =\", items2int([\"milk\", \"butter\"], num_items))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 自定义函数：判断数据集是否是另一个集合的子集"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['milk', 'butter'] is ['milk', 'bread', 'butter'] subset => True\n"
     ]
    }
   ],
   "source": [
    "def is_subset(sx, sy):\n",
    "    for x in sx:\n",
    "        if x not in sy:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "print(\"['milk', 'butter'] is ['milk', 'bread', 'butter'] subset =>\", is_subset(['milk', 'butter'], ['milk', 'bread', 'butter']))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 自定义函数：支持度support计算"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "milk 的支持度 => 0.4\n"
     ]
    }
   ],
   "source": [
    "def support(item, transactions):\n",
    "    num_trans = len(transactions)\n",
    "    counter = 0\n",
    "    for transaction in transactions:\n",
    "        if is_subset(item, transaction):\n",
    "            counter += 1\n",
    "    return counter / num_trans\n",
    "\n",
    "print(\"milk 的支持度 =>\", support(['milk'], transactions))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.关联规则实现一：暴力搜索"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "阈值为3时，所有的频繁集=> [['butter'], ['milk'], ['bread'], ['milk', 'bread']]\n",
      "耗费时间为 => 0.0 seconds\n"
     ]
    }
   ],
   "source": [
    "start_time = time.time()\n",
    "\n",
    "sup = 0.3\n",
    "num_trans = len(transactions)\n",
    "freq_sets = []\n",
    "# 商品子集有 2 的 5 次方个\n",
    "for i in range(1, 2 ** num_items):\n",
    "    subset = int2items(i, num_items)\n",
    "    freq = support(subset, transactions)\n",
    "    if freq > sup:\n",
    "        freq_sets.append(subset)\n",
    "\n",
    "end_time = time.time()\n",
    "print(\"阈值为0.3时，所有的频繁集=>\", freq_sets)\n",
    "print(\"耗费时间为 =>\", end_time - start_time , \"seconds\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.关联规则实现二：基于广度优先遍历的Apriori算法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "top== []\n",
      "cur_set== ['diapers']\n",
      "id== 1\n",
      "freq== 0.2\n",
      "cur_set== ['butter']\n",
      "id== 2\n",
      "freq== 0.4\n",
      "cur_set== ['milk']\n",
      "id== 4\n",
      "freq== 0.4\n",
      "cur_set== ['beer']\n",
      "id== 8\n",
      "freq== 0.2\n",
      "cur_set== ['bread']\n",
      "id== 16\n",
      "freq== 0.6\n",
      "--------------------\n",
      "top== ['butter']\n",
      "cur_set== ['butter', 'diapers']\n",
      "id== 3\n",
      "freq== 0.0\n",
      "cur_set== ['butter', 'milk']\n",
      "id== 6\n",
      "freq== 0.2\n",
      "cur_set== ['butter', 'beer']\n",
      "id== 10\n",
      "freq== 0.0\n",
      "cur_set== ['butter', 'bread']\n",
      "id== 18\n",
      "freq== 0.2\n",
      "--------------------\n",
      "top== ['milk']\n",
      "cur_set== ['milk', 'diapers']\n",
      "id== 5\n",
      "freq== 0.0\n",
      "cur_set== ['milk', 'butter']\n",
      "id== 6\n",
      "freq== 0.2\n",
      "cur_set== ['milk', 'beer']\n",
      "id== 12\n",
      "freq== 0.0\n",
      "cur_set== ['milk', 'bread']\n",
      "id== 20\n",
      "freq== 0.4\n",
      "--------------------\n",
      "top== ['bread']\n",
      "cur_set== ['bread', 'diapers']\n",
      "id== 17\n",
      "freq== 0.0\n",
      "cur_set== ['bread', 'butter']\n",
      "id== 18\n",
      "freq== 0.2\n",
      "cur_set== ['bread', 'milk']\n",
      "id== 20\n",
      "freq== 0.4\n",
      "cur_set== ['bread', 'beer']\n",
      "id== 24\n",
      "freq== 0.0\n",
      "--------------------\n",
      "top== ['milk', 'bread']\n",
      "cur_set== ['milk', 'bread', 'diapers']\n",
      "id== 21\n",
      "freq== 0.0\n",
      "cur_set== ['milk', 'bread', 'butter']\n",
      "id== 22\n",
      "freq== 0.2\n",
      "cur_set== ['milk', 'bread', 'beer']\n",
      "id== 28\n",
      "freq== 0.0\n",
      "--------------------\n",
      "支持度为0.3时，频繁集为=> [['butter'], ['milk'], ['bread'], ['milk', 'bread']]\n",
      "耗费时间为 => 0.0029916763305664062 seconds\n"
     ]
    }
   ],
   "source": [
    "start_time = time.time()\n",
    "\n",
    "sup = 0.3\n",
    "searched = set()   # 子集对应的整数值\n",
    "freq_sets = []     # 符合条件的频繁集\n",
    "queue = []         # 存储临时的子集，用于后续判断\n",
    "queue.append([])\n",
    "head, tail = 0, 1\n",
    "while(head < tail):\n",
    "    top = queue[head]\n",
    "    print(\"top==\", top)\n",
    "    head += 1\n",
    "    for i in items:\n",
    "        if i in top:\n",
    "            continue\n",
    "        cur_set = top + [i]\n",
    "        print(\"cur_set==\", cur_set)\n",
    "        id = items2int(cur_set, num_items)\n",
    "        print(\"id==\", id)\n",
    "        freq = support(cur_set, transactions)\n",
    "        print(\"freq==\", freq)\n",
    "        # 删除不符合条件的子集，符合条件的进入下一轮计算\n",
    "        if freq > sup and id not in searched:\n",
    "            freq_sets.append(cur_set)\n",
    "            queue.append(cur_set)\n",
    "            searched.add(id)\n",
    "            tail += 1\n",
    "    print(\"--------------------\")\n",
    "\n",
    "end_time = time.time()\n",
    "print(\"支持度为0.3时，频繁集为=>\", freq_sets)\n",
    "print(\"耗费时间为 =>\", end_time - start_time , \"seconds\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
